package com.leetcode.www;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
 *
 * 假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
 *
 * 例如，基因序列由"AACCGGTT"变化至"AACCGGTA"即发生了一次基因变化。
 *
 * 与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
 *
 * 现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
 *
 * 注意：
 *
 * 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
 * 如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
 * 假定起始基因序列与目标基因序列是不一样的。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-genetic-mutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-19
 * Time:17:39
 */
public class BFS433 {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> b = new HashSet<>();//基因库
        for(String s: bank){
            b.add(s);
        }
        Set<String> set = new HashSet<>();//标记
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();//保存的基因个数
            while(size-- != 0){
                String s = queue.poll();
                for(int i = 0;i < s.length();i ++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'A';c <= 'Z';c ++){
                        sb.setCharAt(i,c);//修改每个位置的字符
                        String cur = sb.toString();

                        if(set.contains(cur) || !b.contains(cur)){
                            continue;//没在基因库或者已经使用过了
                        }
                        if(cur.equals(end)){//找到了
                            return count + 1;
                        }
                        set.add(cur);//标记已使用
                        queue.offer(cur);//放入队列继续搜索
                    }
                }
            }
            count++;
        }
        return -1;//没有找到
    }
}
